package 动态规划.整数拆分;

/**
 * @author: wh(1835734390 @ qq.com)
 * @date: 2023/2/10 16:11
 * @description:
 * @version:
 */
public class Solution {
    public static void main(String[] args) {
        System.out.println(integerBreak(6));
    }

    //2 <= n <= 58
    //动态规划
    public static int integerBreak(int n) {
        //从0开始的，所以初始化数组大小应该加1
        int[] dp = new int[n + 1];
        for (int i = 2; i <= n; i++) {
            int curMax = 0;
            for (int j = 1; j < i; j++) {
                //两种情况，i-j可以拆分||i-j不可以拆分
                curMax = Math.max(curMax, Math.max(j * (i - j), j * dp[i - j]));
            }
            dp[i] = curMax;
        }
        return dp[n];
    }
}
